// https://leetcode.cn/problems/valid-triangle-number/description/

// 算法思路总结：
// 1. 先对数组进行排序
// 2. 固定最长边，使用双指针寻找有效组合
// 3. 如果两边之和大于第三边，统计所有有效组合
// 4. 时间复杂度：O(n²)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        int n = nums.size(), ret = 0;;
        sort(nums.begin(), nums.end());

        for (int i = n - 1 ; i >= 2 ; i--)
        {
            int l = 0, r = i - 1;
            while (l != r)
            {
                if (nums[l] + nums[r] > nums[i])
                {
                    ret += r - l;
                    r--;
                }
                else l++;
            }
        }

        return ret;
    }
};

int main()
{
    vector<int> v1 = {2,2,3,4}, v2 = {4,2,3,4};
    Solution sol;

    cout << sol.triangleNumber(v1) << endl;
    cout << sol.triangleNumber(v2) << endl;

    return 0;
}